#polyalphabetic cracker
#assumes character string was encoded with a Vignere cipher. 
#Works by splitting a tring into 4 sub strings(since 4 ciphers are being used)
#then finds most likely Caeser cipher shift for each of those substrings. 
#Once it  has each shift, it forms a key using those shifts and passes it to decipher, which is a Vignere decoder.
characters = 'abcdefghijklmnopqrstuvwxyz'
class VigCracker():

	#encodes a string using a basic caesar cipher
	def encode(self,str,shift):
		ret = []
		for c in str:
			if c.isalpha():
				position = characters.find(c)#find position of char in character list
				position+= shift#increase position based on shift
				position%=len(characters)#shouldnt go past length of characters
				ret.append(characters[position])#add ciphercharacter to return string
			else:
				ret.append(c)
		return ''.join(ret)
		
	#deciphers a basic Vigenere cipher
	def decipher(self,str,key):
		ret = []
		for i in range(0,len(str)):
			current = str[i]#get current char
			if current.isalpha():
				position = characters.find(current)#find position of char in character list
				position-= characters.find(key[i%(len(key))])#decrease position based on current character in the key
				position%=len(characters)#shouldnt go past length of characters
				ret.append(characters[position])#add ciphercharacter to return string
			else:
				ret.append(current)
		return ''.join(ret)
		
	#language data taken from http://smurfoncrack.com/pygenere/pygenere.py
	lang_data = {'A':8.167, 'B':1.492, 'C':2.782, 'D':4.253, 'E':12.702,'F':2.228, 'G':2.015,'H':6.094, 'I':6.996, 'J':0.153,'K':0.772, 'L':4.025, 'M':2.406, 'N':6.749, 'O':7.507,'P':1.929, 'Q':0.095, 'R':5.987, 'S':6.327, 'T':9.056,'U':2.758, 'V':0.978, 'W':2.360, 'X':0.150, 'Y':1.974,'Z':0.074, 'max_val':12.702}
	#get every nth char in a string	
	def getEveryNthChar(self,str, start, n):
		result = []
		for i in range(len(str)):
			if (i%n) == start:
				result.append(str[i])
		return result
	#count frequency of each char in a string	
	def countCharFreq(self,str):
		dict = {}
		str = str.upper()
		for c in str:
			if c.isalpha():
				dict[c] = dict.get(c,0)+1
		return dict
	#scale the items in a dictionary using the lang_data's max value in order to make them match lang_data's values
	def scale(self,dict):
		x = sorted(dict.values())
		maxVal = 1
		#print(x)
		if(len(x)>1):
			maxVal = x[-1]
		if(len(x)==1):
			maxVal = x[0]
		factor = self.lang_data['max_val']/maxVal
		for (k,v) in dict.items():
			dict[k] = v*factor
		return dict
	#computes how close a dictionary order is to lang_Data order
	def residualsSquared(self,dict):
		total = 0
		for(k,v) in dict.items():
			total +=(v-self.lang_data[k])**2
		return total
	#find which caeser cipher shift is closest to normal english character distributions
	def findBestCaesar(self,str):
		best = 0
		smallestSum = -1
		for shift in range(26):
			encoded = self.encode(str,shift)
			charFrequencies=self.countCharFreq(encoded)
			scaled = self.scale(charFrequencies)
			sum = self.residualsSquared(scaled)
			if smallestSum == -1:
				smallestSum = sum
			if sum<smallestSum:
				best = shift
				smallestSum = sum
		return best
	#find the key used to encode the cipher	
	def findKey(self,str,keyLen):
		
		key = []
		for i in range(keyLen):
			temp = self.getEveryNthChar(str,i,keyLen)
			acc = []
			for c in temp:
				if c.isalpha():
					acc.append(c)
			alphaOnly = ''.join(acc)#only processes alphabetic characters
			shift = self.findBestCaesar(alphaOnly)#shift is how much of a shift the Caeser cipher used
			if shift ==0:
				key.append('A')#0 corresponds with a
			else:
				key.append(chr(ord('A') + (26-shift)))#otherwise adds the correct character based on what the shift is

		return ''.join(key)
	#crack a given message. this is the function you call externally to start the process. give it the string to be decoded
	def crack_string(self,text):
		key = self.findKey(text,4)
		key = key.lower()
		#print(key)
		return self.decipher(text,key)